package StringAlgorithm;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class leet_20 {
    public static void main(String[] args) {
        String a = "([])";
        Solution_20 p =new Solution_20();
        boolean result = p.isValid(a);
        System.out.println(result);
    }
}


class Solution_20 {
    public boolean isValid(String s) {
        Map<String, String> symbolMap = new HashMap<>();
        symbolMap.put(")", "(");
        symbolMap.put("]", "[");
        symbolMap.put("}", "{");

        Map<String, Integer> prioritySymbolMap = new HashMap<>();
        prioritySymbolMap.put("(", 1);
        prioritySymbolMap.put("[", 2);
        prioritySymbolMap.put("{", 3);

        Stack<String> stack = new Stack();
        for(int i=0; i<s.length(); i++){
            String tmpValue = String.valueOf(s.charAt(i));
            if(symbolMap.containsKey(tmpValue)){
                // 如果字典中存在这个键就把栈顶元素抛出
                if(stack.isEmpty()){
                    // 栈为空代表 右括号先于左括号出现
                    return false;
                }
                String sybol = stack.pop();
                String value = symbolMap.get(tmpValue);
                if(!sybol.equals(value)){
                    // 右括号前面没有左括号出现出现问题
                    return false;
                }
            }else {
                // 栈顶的符号优先
                String sybol = stack.peek();
                int value = prioritySymbolMap.get(sybol);

                // 即将入栈的符号优先级
                int value_2 = prioritySymbolMap.get(tmpValue);
                if(value_2>value){
                    // 如果我 栈顶是( 入栈的是 [ 肯定括号的顺序错误
                    return false;
                }
                stack.push(tmpValue);
            }
        }
        if(!stack.isEmpty()){return false;}
        return true;
    }
}